package sort.quicksort.leetcode;

import org.junit.Test;

import java.util.Random;

/**
 * @Description 给定一个无序数组，在不排序的情况下找到中位数
 * @Author Firenut
 * @Date 2023-08-05 19:06
 */
public class Search_median {
    Random random = new Random(System.currentTimeMillis());

    @Test
    public void test() {
//        int[] nums = new int[]{1, 7, 3, 2, 6};        // 1 2 3 6 7
        int[] nums = new int[]{3, 1, 4, 1, 5, 9, 2, 6}; // 1 1 2 3 4 5 6 9
        if (nums.length % 2 == 0) {
            // 需要计算中间的两个数，取平均值
            int left = findMid(nums, 0, (nums.length - 1) / 2, nums.length - 1);
            int right = findMid(nums, 0, nums.length / 2, nums.length - 1);
            double pivot = nums[left] + (nums[right] - nums[left]) / 2.0;
            System.out.println(pivot);
        }else{
            int index = findMid(nums, 0, (nums.length - 1) / 2, nums.length - 1);
            System.out.println(nums[index]);
        }
    }

    int findMid(int[] nums, int left, int mid, int right) {
        int pivot = 0;
        while (pivot != mid) {
            pivot = partition(nums, left, right);
            if (pivot < mid) {
                left = pivot + 1;
            } else if (pivot == mid) {
                return nums[pivot];
            } else {
                right = pivot - 1;
            }
        }
        return -1;
    }

    int partition(int nums[],int left,int right) {
        int le = left + 1, gt = right;
        int index = left + random.nextInt(right - left + 1);
        swap(nums, left, index);
        int pivot = nums[left];
        while (le <= gt) {
            while (le <= gt && nums[le] < pivot) {
                le++;
            }
            while (le <= gt && nums[gt] > pivot) {
                gt--;
            }
            if(le>=gt) break;
            swap(nums, le, gt);
            le++;
            gt--;
        }
        swap(nums, left, gt);
        return gt;
    }

    void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
